package algorithm;

/**
 * 买股票的最佳时机II
 * 与121的相比，在持股这种情况有点不一样
 *  121. 持股，必然是-prices[i]，因为只能进行一次交易
 *  122. 持股，今天买入，但是前面可能已经交易过了，所以这个地方是dp[i - 1][0] - prices[i]
 */
public class LeetCode_maxProfit_122 {
    /**
     * 可行
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0 ;
        dp[0][1] = -prices[0];

        int res = 0;
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }

    /**
     * 内存优化
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices, boolean noUsed) {
        int len = prices.length;
        int[] dp = new int[2];
        int yesterday0, yesterday1;
        yesterday0 = 0 ;
        yesterday1 = -prices[0];

        int res = 0;
        for (int i = 1; i < len; i++) {
           dp[0] = Math.max(yesterday0, yesterday1 + prices[i]);
           dp[1] = Math.max(yesterday1, yesterday0 - prices[i]);
           yesterday0 = dp[0];
           yesterday1 = dp[1];
        }
        return dp[0];
    }

    /**
     * 贪心算法
     * @param prices
     * @param noUsed
     * @param noUsedToo
     * @return
     */
    public int maxProfit(int[] prices, boolean noUsed, boolean noUsedToo) {
        int len = prices.length;
        int res = 0;
        for (int i = 1; i < len; i++) {
            res += Math.max(0, prices[i] - prices[i - 1]);
        }
        return res;
    }

}
